package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2022/3/23.<br><br>
 *
 * 中断：递增的三元子序列
 */
public class Topic334 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution2();

        int[] array = new int[] {1,2,3,4,5};
        System.out.println(solution.increasingTriplet(array));

        array = new int[] {5,4,3,2,1};
        System.out.println(solution.increasingTriplet(array));

        array = new int[] {2,1,5,0,4,6};
        System.out.println(solution.increasingTriplet(array));

        array = new int[] {4,5,2147483647,1,2};
        System.out.println(solution.increasingTriplet(array));
    }

    private interface BaseSolution {
        boolean increasingTriplet(int[] nums);
    }

    /**
     * 贪心算法
     */
    private static class Solution1 implements BaseSolution {

        @Override
        public boolean increasingTriplet(int[] nums) {
            int len = nums.length;

            if(len < 3) {
                return false;
            }

            int first = nums[0];
            int second = Integer.MAX_VALUE;
            for(int i = 1; i < len; i++) {
                if(nums[i] > second) {
                    return true;
                }
                else if(nums[i] > first) {
                    second = nums[i];
                }
                else if(nums[i] < first) {
                    first = nums[i];
                }
            }

            return false;
        }
    }

    private static class Solution2 implements BaseSolution {

        @Override
        public boolean increasingTriplet(int[] nums) {
            int len = nums.length;
            if(len < 3) {
                return false;
            }

            int[] leftArray = new int[len];
            leftArray[0] = nums[0];
            for(int i = 1; i < len; i++) {
                leftArray[i] = Math.min(leftArray[i - 1], nums[i]);
            }

            int[] rightArray = new int[len];
            rightArray[len - 1] = nums[len - 1];
            for(int i = len - 2; i >= 0; i--) {
                rightArray[i] = Math.max(rightArray[i + 1], nums[i]);
            }

            for(int i = 1; i < len; i++) {
                if(nums[i] > leftArray[i] && nums[i] < rightArray[i]) {
                    return true;
                }
            }

            return false;
        }
    }
}
